package com.wtgroup.demo.mianshi.算法.链表;

import com.wtgroup.demo.common.bean.LinkNode;
import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;


/**
 * 定位到中间位置, 奇数中间, 偶数上中点
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/2 11:38
 */
public class Q_链表中点 {
    public static void main(String[] args) {
        Judger.of(() -> {
                    LinkNode[] linkNodes = mockLinkList();
                    LinkNode head = linkNodes[0];
                    LinkNode middle = linkNodes[1];

                    LinkNode res = getMiddleNode(head);
                    if (res != middle) {
                        if (head != null) head.print();
                        else System.out.println("nullllllllllll");
                    }
                    return res == middle;
                })
                .setIterCount(1000)
                .start()
                .print();
    }

    // 推荐
    static LinkNode getMiddleNode(LinkNode head) {
        if (head ==null) {
            return head;
        }
        // 上来就定义 快慢指针, 不关心多少个 ndoe

        LinkNode slow,fast;
        slow = fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    static LinkNode getMiddleNode_bak(LinkNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        LinkNode slow = head;
        LinkNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next; // >>2
        }

        return slow;
    }

    static LinkNode[] mockLinkList() {
        int len = RandomUtil.randomInt(0, 10);
        // int[] ints = RandomUtil.randomArray(len, 0, 100);
        int[] ints = {79, 85, 97, 35, 97, 62, 68, 60};
        LinkNode head = null;
        LinkNode tail = head;
        LinkNode middle = head;
        for (int i = 0; i < ints.length; i++) {
            if (head == null) {
                tail = head = new LinkNode(ints[i]);
            } else {
                tail = tail.next = new LinkNode(ints[i]);
            }
            if (i == (ints.length-1) / 2) {
                // 中点节点
                middle = tail;
            }
        }

        return new LinkNode[]{head, middle};
    }

}
